import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

import Datastructure.*;


/**
 * Hauptklasse, diese wird aufgerufen
 * 
 */
public class simplex {
	
	//final double eps=1E-7;
	Converter conv;
	
	ArrayList<ArrayList<Entry>> A;
	ArrayList<ArrayList<Entry>> AT;
	ArrayList<Entry> b;
	ArrayList<Entry> c;
	ArrayList<ArrayList<Entry>> inv_AB;//AB^-1, inv_AB.get(i)=i-te Zeile, noetig fuer inv_AB*...
	ArrayList<ArrayList<Entry>> inv_ABT;//AB^-1, inv_AB.get(i)=i-te Spalte, noetig fuer ...*inv_AB
	double price;//Zielfunktionswert
	ArrayList<Entry> b_;//Zielvektor xB
	
	//Basis/Nicht-Basis-Variablen
	int[] base;
	int[] notbase;
	
	
	public simplex(String filename){
		conv=new Converter();
		/*
		 * c
		 * A b
		 * s
		 */
		ArrayList<ArrayList<Entry>> matrix=conv.convert(filename);
		
		//s
		ArrayList<Entry> signum=matrix.get(matrix.size()-1);
		
		int posCol=matrix.get(0).get(matrix.get(0).size()-1).getPosition();//==numOfColumns
		
		//c
		this.c=matrix.get(0);
		c.remove(c.size()-1);
		for(int i=0;i<c.size();i++){
			c.get(i).setValue(-c.get(i).getValue());
		}
		
		//b
		this.b=matrix.get(matrix.size()-2);
		
		//A, mit Schlupfvariablen
		A=new ArrayList<ArrayList<Entry>>();

		int counter=0;
		
		//LP => standard form Ax=b
		for(int i=1;i<matrix.size()-2;i++){
			A.add(matrix.get(i));
			
			ArrayList<Entry> tmp=A.get(i-1);
			
			int sgnpos=find(signum,i-1);
			
			if(sgnpos==-1)
				continue;
			
			if(signum.get(sgnpos).getValue()==1){ //a*x>=b => a*x-y=b
				tmp.add(new Entry(posCol-1+counter, -1));
				counter++;
				
				int bPos=find(b,i-1);
				if(bPos>0 && b.get(bPos).getValue()<0){//ax-y=b<0 => -ax+y=|b|
					for(int j=0;j<tmp.size();j++){
						tmp.get(j).setValue(-tmp.get(j).getValue());
					}
					b.get(bPos).setValue(-b.get(bPos).getValue());
				}
				signum.get(sgnpos).setValue(0);
			}
			else if(signum.get(sgnpos).getValue()==-1){//ax<=b => ax+y=b
				tmp.add(new Entry(posCol-1+counter, 1));
				counter++;
				
				int bPos=find(b,i-1);
				if(bPos>0 && b.get(bPos).getValue()<0){//ax-y=b<0 => -ax+y=|b|
					for(int j=0;j<tmp.size();j++){
						tmp.get(j).setValue(-tmp.get(j).getValue());
					}
					b.get(bPos).setValue(-b.get(bPos).getValue());
				}
				signum.get(sgnpos).setValue(0);
			}
		}
		
		AT=transformMatrix(A);
	}
	
	/**
	 * Konstruktor fuer Phase 1
	 * @param A
	 * @param b
	 * @param c
	 */
	public simplex(ArrayList<ArrayList<Entry>> A, ArrayList<Entry> b, ArrayList<Entry> c){
		this.A=A;
		this.b=b;
		this.c=c;
	}
	
	/**
	 * Phase I
	 * find an allowed base
	 * @return 1, if base is found, 0 if P=(A,b)={x} or -1, if empty
	 * @throws Exception 
	 */
	public int phaseOne() throws Exception{
		long zeit=System.currentTimeMillis();
		ArrayList<Entry> costs=new ArrayList<Entry>();
		simplex sp1=new simplex((ArrayList<ArrayList<Entry>>)A.clone(),(ArrayList<Entry>)b.clone(),costs);
		int cols=this.AT.size();//number of Columns
		sp1.base=new int[A.size()];
		sp1.notbase=new int[cols];
		
		//Schlupfvariablen
		for(int i=0;i<sp1.A.size();i++){
			sp1.A.get(i).add(new Entry(cols+i,1));
			sp1.c.add(new Entry(cols+i,-1));
			sp1.base[i]=cols+i;
		}
		for(int i=0;i<sp1.notbase.length;i++){
			sp1.notbase[i]=i;
		}
		sp1.AT=transformMatrix(sp1.A);
		sp1.inv_ABT=subMatrix(sp1.AT, sp1.base);
		sp1.inv_AB=transformMatrix(sp1.inv_ABT);
		sp1.b_=(ArrayList<Entry>) sp1.b.clone();
		/*
		 * Simplex-Verfahren anwenden
		 * 1. Basis ist cols,...,cols+A.size()-1, b_=b, inv_AB=I
		 * =>Phase II
		 */
		ArrayList<Entry> pi=new ArrayList<Entry>();
		int counter=0;
		boolean infinite=false;
		boolean opt=false;
		
		while(!infinite && !opt){
			counter++;
			pi=sp1.btran();
			
			int s=sp1.price(pi);
			if(s<0){
				opt=true;
				//System.out.println("opt");
				break;
			}
			ArrayList<Entry> d_=sp1.ftran(s);
			int r=sp1.chuzr(d_);
			if(r<0){
				infinite=true;
				System.out.println("infinite in phase 1, r<0");
				break;
			}
			sp1.wreta(r,s, d_);
			if(System.currentTimeMillis()-zeit>30000)
				throw new Exception();
		}
		//nach Phase 1: pruefe, ob (1^T*b-1^T*y=) 1^T*Ax<1^T*b, dann leer. <=> xi=0 fuer i>=cols 
		for(int i=cols;i<A.size();i++){
			int k=sp1.find(sp1.b_, i);
			if(k==-1)
				continue;
			if(sp1.b_.get(k).getValue()!=0){
				return -1;
			}
		}
		
		boolean based=false;
		boolean notbased=false;
		
		while(!based && !notbased){
			based=true;
			notbased=true;
			//eig. B Teilmenge von {1,...,cols}
			for(int i=0;i<sp1.base.length;i++){
				if(sp1.base[i]>=cols){
					based=false;
					break;
				}
			}
			for(int i=0;i<sp1.notbase.length;i++){
				if(sp1.notbase[i]<cols){
					notbased=false;
					break;
				}
			}
			//base from the phase-one-simplex is allowed for this simplex => only adjust notbase 
			if(based && !notbased){
				this.inv_AB=sp1.inv_AB;
				this.inv_ABT=transformMatrix(this.inv_AB);
				this.b_=sp1.b_;
				this.base=sp1.base;
				this.notbase=new int[cols-this.base.length];
				int countnb=0;
				for(int i=0;i<sp1.notbase.length;i++){
					if(sp1.notbase[i]<cols){
						this.notbase[countnb]=sp1.notbase[i];
						countnb++;
					}
				}
				return 1;
			}
			//P(A,b)={x}={A^-1*b}
			if(based && notbased){
				//Bc{1,...,n} und N&{1,...,n} leer => B={1,...,n}, n=m und inv_AB=inv(A)
				this.inv_AB=sp1.inv_AB;
				this.inv_ABT=transformMatrix(this.inv_AB);
				this.b_=sp1.b_;
				this.base=sp1.base;
				this.notbase=new int[0];
				return 0;
			}
			//Basisloesung ist degeneriert
			
			int artNum=0;//number of artificial variables
			//I.4
			boolean operated=false;
			
			for(int i=0;i<sp1.base.length;i++){
				if(sp1.base[i]>=cols){
					artNum++;
					//evtl. Auswahl verbessern
					ArrayList<Entry> mult=multiply(sp1.inv_AB.get(i),subMatrix(sp1.AT, sp1.notbase));
					for(int j=0;j<mult.size();j++){
						
						if(sp1.notbase[mult.get(j).getPosition()]>=cols)//Schlupfvariablen sollten nicht ausgetauscht werden
							continue;
						
						if(mult.get(j).getValue()!=0){
							operated=true;
							int s=mult.get(j).getPosition();
							ArrayList<Entry> d=sp1.ftran(s);
							sp1.wreta(i, s, d);
							break;//Update ausgefuehrt=> zur naechsten Schlupfvariable
						}
					}
				}
			}
			//I.5
			if(!operated){
				int[] rows=new int[artNum];
				
				//Schritt 1: sortiere die Zeilen
				int tmp=0;
				for(int i=sp1.base.length-1;i>=0;i--){
					if(sp1.base[i]<cols){
						continue;
					}
					rows[tmp]=i;
					tmp++;
					sp1.inv_AB.remove(i);
				}
				sp1.inv_ABT=transformMatrix(sp1.inv_AB);
				for(int i=sp1.base.length-1;i>=0;i--){
					if(sp1.base[i]<cols){
						continue;
					}
					sp1.inv_ABT.remove(i);
				}
				this.inv_AB=transformMatrix(sp1.inv_ABT);
				this.inv_ABT=sp1.inv_ABT;
				
				//Basis aktualisieren
				int[] newBase=new int[sp1.base.length-artNum];
				int count=0;
				for(int i=0;i<sp1.base.length;i++){
					if(sp1.base[i]<cols){
						newBase[count]=sp1.base[i];
						count++;
					}
				}
				//A'=A(I,.)
				for(int i=0;i<rows.length;i++){
					this.A.remove(rows[i]);
				}
				this.AT=transformMatrix(this.A);
				ArrayList<Entry> xB=subVector(sp1.b_, newBase);
				this.base=newBase;
				this.b_=xB;
				//P=(A,b)={x}
				if(sp1.base.length-artNum==cols){
					this.notbase=new int[0];
					return 0;
				}
				else{
					
					this.notbase=new int[cols-this.base.length];
					int count2=0;
					for(int i=0;i<this.AT.size();i++){
						boolean inBase=false;
						for(int j=0;j<this.base.length;j++){
							if(this.base[j]==i){
								inBase=true;
								break;
							}
						}
						if(!inBase){
							try{
							this.notbase[count2]=i;
							}
							catch(ArrayIndexOutOfBoundsException e){
								//System.out.println("count2, notbase.length: "+count2+" | "+notbase.length+", "+base.length);
							}
							count2++;
						}
					}
					return 1;
				}
			}
		}
		return -1;
	}
	
	
	//BTRAN, PRICE, FTRAN, CHUZR, WRETA
	
	/**
	 * calculate the shadow prices
	 * @return shadow prices
	 */
	public ArrayList<Entry> btran(){
		//cB'*inv_AB
		return multiply(subVector(c,base),inv_ABT);
	}
	
	/**
	 * calculate the reduced cost and find an index s with c_s>0
	 * @param pi shadow price from btran
	 * @return index s with c_s>0 or -1, if no such index exists
	 */
	public int price(ArrayList<Entry> pi){
		/*
		 * berechne reduzierte Kosten c_j:=(cN')j-pi'AN*ej
		 * waehle Index s mit cs>0
		 */
		//c_=c1-c2
		ArrayList<Entry> c1=subVector(c, notbase);
		ArrayList<Entry> c2=multiply(pi,subMatrix(AT, notbase));
		double max=0;
		int s=-1;
		//every entry of c2 is zero
		if(c2.size()==0){
			for(int i=0;i<c1.size();i++){
				if(c1.get(i).getValue()>max){
					max=c1.get(i).getValue();
					s=c1.get(i).getPosition();
				}
			}
			
			return s;
		}
		
		if(c1.size()==0){
			for(int i=0;i<c2.size();i++){
				if(-c2.get(i).getValue()>max){
					max=-c2.get(i).getValue();
					s=c2.get(i).getPosition();
				}
			}
			return s;
		}
		
		int p2=0;
		int pos2=c2.get(0).getPosition();
		
		for(int i=0;i<c1.size();i++){
			int pos=c1.get(i).getPosition();
			
			while(pos2<pos){
				if(p2>=c2.size())
					break;
				double val=-c2.get(p2).getValue();
				if(val>max){
					s=pos2;
					max=val;
				}
				p2++;
				if(p2>=c2.size()){
					break;
				}
				pos2=c2.get(p2).getPosition();
			}
			
			if(pos==pos2){
				double val=c1.get(i).getValue()-c2.get(p2).getValue();
				if(val>max){
					s=pos;
					max=val;
				}
				p2++;
				if (p2>=c2.size()){
					break;
				}
				pos2=c2.get(p2).getPosition();
			}
			else{
				double val=c1.get(i).getValue();
				if(val>max){
					s=pos;
					max=val;
				}
			}
		}
		//letzter Eintrag von c1 kleiner als der von c2
		for(int i=0;i<c2.size();i++){
			Entry e=c2.get(i);
			if(e.getPosition()>c1.get(c1.size()-1).getPosition() && -e.getValue()>max){
				max=-e.getValue();
				s=e.getPosition();
			}
		}
		return s;
	}
	
	/**
	 * inv_AB*A(.,qs)
	 * @param s index
	 * @return
	 */
	public ArrayList<Entry> ftran(int s){
		/*
		 * d_:= inv_AB*A(.,notBase[s])
		 */
		ArrayList<Entry> d_=new ArrayList<Entry>();
		
		ArrayList<Entry> Aqs=transformMatrix(A).get(notbase[s]);
		
		for(int i=0;i<inv_AB.size();i++){
			ArrayList<Entry> a=inv_AB.get(i);
			double tmp=multiplyVectrices(a, Aqs);
			if(tmp!=0){
				d_.add(new Entry(i, tmp));
			}
		}
		return d_;
	}
	
	/**
	 * choose row
	 * @param d pivot column from ftran
	 * @return row where bi/di is minimal
	 */
	public int chuzr(ArrayList<Entry> d){
		double y0=Double.POSITIVE_INFINITY;
		int countb=0;
		int posb=b_.get(0).getPosition();
		ArrayList<Integer> list=new ArrayList<Integer>();//for possible rows
		
		for(int i=0;i<d.size();i++){
			if(d.get(i).getValue()<=0)
				continue;
			int posd=d.get(i).getPosition();
			
			while(posb<posd){
				countb++;
				if(countb>=b_.size()){//=> all other entries of b_ have value 0 => b_i/di=0 
					break;
				}
				posb=b_.get(countb).getPosition();
			}
			if(posb==posd){
				double val=b_.get(countb).getValue()/d.get(i).getValue();
				if(val<y0){
					list.clear();
					y0=val;
					list.add(posd);
				}
				else if(val==y0){
					list.add(posd);
				}
			}
			else if(posb>posd ||(countb>=b_.size() && posd>posb)){//=> di>0, bi=0 => y0=0
				if(0<y0){
					list.clear();
					y0=0;
					list.add(posd);
				}
				else if(0==y0){
					list.add(posd);
				}
			}
		}
		if(list.size()==0){//no index in list => di<=0 for all i
			return -1;
		}
		
		int row=-1;
		ArrayList<Entry> ar=new ArrayList<Entry>();
		for(int i=0;i<list.size();i++){
			double ais=d.get(find(d,list.get(i))).getValue();
			if(ais<=0)
				continue;
			
			ArrayList<Entry> tmp=multiply(inv_AB.get(i), AT);
			for(int j=0;j<tmp.size();j++){
				tmp.get(j).setValue(tmp.get(j).getValue()/ais);
			}
			//no minimum=> current element is minimum
			if(ar.size()==0){
				ar=tmp;
				row=list.get(i);
				continue;
			}
			int lmin=lexmin(ar,tmp);//1<=> ar>tmp
			if(lmin==1){
				ar=tmp;
				row=list.get(i);
			}
		}
		return row;
	}
	
	/**
	 * update the base
	 * @param r pivot row
	 * @param s pivot column
	 * @param d vector from ftran
	 */
	public void wreta(int r, int s, ArrayList<Entry> d){
		//create eta vector
		ArrayList<Entry> eta=new ArrayList<Entry>();
		int blubb=find(d, r);
		
		//System.out.println("r,s: "+r+", "+s+" | "+base[r]+", "+notbase[s]);
		
		double ars_=0;
		if(blubb>=0){
			ars_=d.get(blubb).getValue();
		}
		
		if(ars_==0 &&blubb==-1){
			System.out.println("AAHH");
		}
		else if(ars_==0 && blubb>=0)
			System.out.println("O____O");
		for(int i=0;i<d.size();i++){
			if(d.get(i).getPosition()==r){
				eta.add(new Entry(r,1/ars_));
			}
			else{
				int pos=d.get(i).getPosition();
				double val=d.get(i).getValue();
				eta.add(new Entry(pos,-val/ars_));
			}
		}
		int tmp=base[r];
		base[r]=notbase[s];
		notbase[s]=tmp;
		ArrayList<Entry> etaRow=new ArrayList<Entry>();//(m,m)-Matrix
		ArrayList<ArrayList<Entry>> tmpAB=new ArrayList<ArrayList<Entry>>();
		ArrayList<Entry> tmpb_=new ArrayList<Entry>();
		int oldposAB=0;
		int oldposb=0;
		for(int i=0;i<eta.size();i++){
			int etapos=eta.get(i).getPosition();
			
			while(oldposAB<etapos){
				ArrayList<Entry> al=new ArrayList<Entry>();
				for(int l=0;l<inv_AB.get(oldposAB).size();l++){
					al.add(new Entry(inv_AB.get(oldposAB).get(l).getPosition(), inv_AB.get(oldposAB).get(l).getValue()));
				}
				tmpAB.add(al);
				oldposAB++;
			}
			while(oldposb<b_.size() &&b_.get(oldposb).getPosition()<etapos){
				tmpb_.add(new Entry(b_.get(oldposb).getPosition(), b_.get(oldposb).getValue()));
				oldposb++;
			}
			if(etapos<r){
				etaRow.add(new Entry(etapos,1));
				Entry e=new Entry(r, eta.get(i).getValue());
				etaRow.add(e);
			}
			else if(etapos==r){
				etaRow.add(new Entry(eta.get(i).getPosition(), eta.get(i).getValue()));
			}
			else{
				Entry e=new Entry(r, eta.get(i).getValue());
				etaRow.add(e);
				etaRow.add(new Entry(etapos,1));
			}
			
			tmpAB.add(multiply(etaRow, inv_ABT));
			oldposAB++;
			
			double valb=multiplyVectrices(etaRow, b_);
			
			if(valb!=0){
				tmpb_.add(new Entry(etapos,valb));
			}
			oldposb++;
			etaRow.clear();
			
			//last not-zero entry of eta, but not the end of inv_AB
			if(i==eta.size()-1 && etapos<inv_AB.size()-1){
				while(oldposAB<inv_AB.size()){
					ArrayList<Entry> al=new ArrayList<Entry>();
					for(int l=0;l<inv_AB.get(oldposAB).size();l++){
						al.add(new Entry(inv_AB.get(oldposAB).get(l).getPosition(), inv_AB.get(oldposAB).get(l).getValue()));
					}
					tmpAB.add(al);
					oldposAB++;
				}
			}
			//similar with b_
			if(i==eta.size()-1 && etapos<b_.get(b_.size()-1).getPosition()){
				while(oldposb<b_.size()){
					tmpb_.add(new Entry(b_.get(oldposb).getPosition(), b_.get(oldposb).getValue()));
					oldposb++;
				}
			}
		}
		
		inv_AB=tmpAB;
		inv_ABT=transformMatrix(inv_AB);
		//b_=tmpb_;
		b_.clear();
		for (int i=0; i<inv_AB.size();i++){
			double val= multiplyVectrices(inv_AB.get(i), b);
			if (val!=0) {
				b_.add(new Entry(i,val));
			}
		}
	}
	
	/**
	 * calculates a^T*b
	 * @param fv first vector
	 * @param sv second vector
	 * @return a^T*b
	 */
	public double multiplyVectrices(ArrayList<Entry> fv, ArrayList<Entry> sv){
		double val=0;
		int posb=sv.get(0).getPosition();
		int counter=0;
		for(int i=0;i<fv.size();i++){
			double vala=fv.get(i).getValue();
			int posa=fv.get(i).getPosition();
			while(posb<posa){
				counter++;
				if(counter>=sv.size()){
					break;
				}
				posb=sv.get(counter).getPosition();
			}
			if(posa==posb){
				val+=vala*sv.get(counter).getValue();
			}
		}
		//return eps*(double)Math.round(val/eps)/*val*/;
		return val;
	}
	
	/**
	 * calculates v*B
	 * @param v vector, dimensions should be (1,m)
	 * @param B matrix, dimensions should be (m,n)
	 * @return v*B
	 */
	public ArrayList<Entry> multiply(ArrayList<Entry> v, ArrayList<ArrayList<Entry>> B){
		ArrayList<Entry> sol=new ArrayList<Entry>();
		
		for(int i=0;i<B.size();i++){
			ArrayList<Entry> m=B.get(i);
			double sum=this.multiplyVectrices(v, m);
			
			if(sum!=0)
				sol.add(new Entry(i,sum));
			
			//if(Math.abs(sum)>eps)
			//	sol.add(new Entry(i, eps*(double)Math.round(sum/eps)/*sum*/));
		}
		return sol;
	}
	
	/**
	 * if the matrix is saved so the initial list represents the rows, change it so the new one is read column-first and vice versa
	 * @param B old matrix
	 * @return new matrix with changed format
	 */
	public ArrayList<ArrayList<Entry>> transformMatrix(ArrayList<ArrayList<Entry>> B){
		
		ArrayList<ArrayList<Entry>> B2=new ArrayList<ArrayList<Entry>>();
		for(int i=0;i<B.size();i++){
			ArrayList<Entry> tmp=B.get(i);
			if(tmp.size()==0)
				continue;
			while(B2.size()<=tmp.get(tmp.size()-1).getPosition()){//adjust size
				B2.add(new ArrayList<Entry>());
			}
			for(int j=0;j<tmp.size();j++){
				Entry node=tmp.get(j);
				B2.get(node.getPosition()).add(new Entry(i,node.getValue()));
			}
		}
		return B2;
	}
	
	/**
	 * creates a submatrix with the specified indices
	 * @param B matrix
	 * @param ar array of indices
	 * @return submatrix of B
	 */
	public ArrayList<ArrayList<Entry>> subMatrix(ArrayList<ArrayList<Entry>> B, int[] ar){
		
		ArrayList<ArrayList<Entry>> M=new ArrayList<ArrayList<Entry>>();
		for(int i=0;i<ar.length;i++){
			M.add(B.get(ar[i]));
		}
		return M;
	}
	
	
	/**
	 * creates a subvector with the specified indices
	 * @param m vector
	 * @param ar array of indices
	 * @return subvector of m
	 */
	public ArrayList<Entry> subVector(ArrayList<Entry> m, int[] ar){
		ArrayList<Entry> tmp=new ArrayList<>();
		for(int i=0;i<ar.length;i++){
			for(int j=0;j<m.size();j++){
				if(m.get(j).getPosition()==ar[i]){
					Entry e=m.get(j).copy();
					e.setPosition(i);
					tmp.add(e);
				}
			}
		}
		return tmp;
	}
	
	/**
	 * shows the positions and values of a list
	 * @param ar list
	 */
	public void show(ArrayList<Entry> ar){
		String outp="";
		String outv="";
		for(int i=0;i<ar.size();i++){
			outp+=(ar.get(i).getPosition()+1)+" ";
			outv+=ar.get(i).getValue()+" ";
		}
		System.out.println(outp+"\n"+outv);
	}
	
	
	public void present(ArrayList<Entry> ar){
		String out="";
		int counter=0;
		for(int i=0;i<ar.size();i++){
			int pos=ar.get(i).getPosition();
			while(counter<pos){
				out+="0.0 ";
				counter++;
			}
			out+=ar.get(i).getValue()+" ";
			counter++;
		}
		System.out.println(out);
	}
	
	public void presentPos(ArrayList<Entry> ar){
		String out="";
		for(int i=0;i<ar.size();i++){
			out+=ar.get(i).getPosition()+" ";
		}
		System.out.println(out);
	}
	
	/**
	 * compares two vectrices and finds out, which one is the lexicographical smaller one
	 * @param t1 first vector
	 * @param t2 second vector
	 * @return 1 if t1>t2, -1 if t1<t2 or 0 if t1=t2 
	 */
	public int lexmin(ArrayList<Entry> t1, ArrayList<Entry> t2){
		
		int count1=0;
		int count2=0;
		int pos1=t1.get(0).getPosition();
		int pos2=-1;
		try{
			pos2=t2.get(0).getPosition();
		}catch(IndexOutOfBoundsException e){
			//t2.size()==0 =>test first entry of t1
			double val=t1.get(0).getValue();
			if(val<0)
				return -1;
			if(val>0)
				return 1;
		}
		while(count1<t1.size() && count2<t2.size()){
			double val1=t1.get(count1).getValue();
			double val2=t2.get(count2).getValue();
			pos1=t1.get(count1).getPosition();
			pos2=t2.get(count2).getPosition();
			if(pos1<pos2){
				if(val1<0){
					return -1;
				}
				else if(val1>0){
					return 1;
				}
				count1++;
			}
			else if(pos2<pos1){
				if(val2<0){
					return 1;
				}
				else if(val2>0){
					return -1;
				}
				count2++;
			}
			else{//pos1==pos2
				double bla=t1.get(count1).getValue()-t2.get(count2).getValue();
				if(bla<0)
					return -1;
				else if(bla>0)
					return 1;
			}
			count1++;count2++;
		}
		//default, should never be reached, because that means that t1=t2
		return 0;
	}
	
	public boolean testbases(){
		boolean[] ar=new boolean[this.base.length+this.notbase.length];
		int[] ar2=new int[this.base.length+this.notbase.length];
		for(int i=0;i<base.length;i++){
			if(ar[base[i]]){
				System.out.println("Fehler Basis "+base[i]+", "+ar2[base[i]]);
				return true;
			}
		}
		return false;
	}
	
	public ArrayList<Entry> order(){
		ArrayList<Entry> list=new ArrayList<Entry>();
		int[] pos=new int[base.length];
		int[] base2=new int[base.length];
		boolean swapped=true;
		
		for(int i=0;i<pos.length;i++){
			pos[i]=i;
			base2[i]=base[i];
		}
		
		while(swapped){
			swapped=false;
			for(int i=0;i<base.length-1;i++){
				int b1=base2[i];
				int b2=base2[i+1];
				if(b1>b2){
					swapped=true;
					base2[i+1]=b1;
					base2[i]=b2;
					int tmp=pos[i];
					pos[i]=pos[i+1];
					pos[i+1]=tmp;
				}
			}
		}
		
		for(int i=0;i<pos.length;i++){
			int k=find(b_, pos[i]);
			if(k<0)
				continue;
			
			Entry e=new Entry(b_.get(k).getPosition(), b_.get(k).getValue());
			e.setPosition(base2[i]);
			list.add(e);
		}
		return list;
	}
	
	/**
	 * find the element in the list with position {@code index}
	 * @param list ArrayList 
	 * @param index wanted position
	 * @return the index {@code found} where list.get(found).getPosition()==index
	 */
	public int find(ArrayList<Entry> list, int index){
		for(int i=0;i<list.size();i++){
			if(list.get(i).getPosition()==index)
				return i;
		}
		return -1;
	}
	
	
	public void test(){
		ArrayList<Entry> b_comp=new ArrayList<Entry>();
		ArrayList<Entry> b2=order();
		
		ArrayList<ArrayList<Entry>> AB=transformMatrix(subMatrix(transformMatrix(A), base));
		for(int i=0;i<AB.size();i++){
			double val=multiplyVectrices(A.get(i), b2);
			if(val!=0)
				b_comp.add(new Entry(i,val));
		}
		double sum=0;
		for(int i=0;i<b_comp.size();i++){
			double tmp=0;
			try{
				tmp=b_comp.get(i).getValue()-b.get(find(b,b_comp.get(i).getPosition())).getValue();
			}
			catch(IndexOutOfBoundsException e){
				tmp=0;
			}
			sum+=(tmp*tmp);
		}
	}
	
	public static void main(String[] args) throws Exception{
		
		try{
			long startzeit=System.currentTimeMillis();
			if(args.length!=2) throw new IllegalArgumentException("simplex <Inputfile> <Outputfile>");
			
			File input = new File(args[0]);
			File output = new File(args[1]);
			
			//does this file exist? 
			if(!input.exists()) throw new IllegalArgumentException("The file does not exist!");
			
			System.out.println("simplex "+args[0]);
			
			simplex simplex=new simplex(args[0]);
			
			boolean infinite=false;
			boolean opt=false;
			
			int p1=simplex.phaseOne();
			if(p1==-1){
				System.out.println("empty");
				return;
			}
			else if(p1==0){
				opt=true;
			}
			
	//		System.out.println("phase one: "+p1+"      ::::::::::::::::::::::::::::::::::::::::::");
			
			for(int i=0;i<simplex.A.size();i++){
				ArrayList<Entry> tmp=simplex.A.get(i);
				tmp.remove(tmp.size()-1);
			}
			
			ArrayList<Entry> pi=new ArrayList<Entry>();
			int counter=0;
			while(!infinite && !opt){
				counter++;
				pi=simplex.btran();
				
				int s=simplex.price(pi);
				if(s<0){
					opt=true;
					break;
				}
				
				ArrayList<Entry> d_=simplex.ftran(s);
				
				int r=simplex.chuzr(d_);
				if(r<0){
					infinite=true;
					break;
				}
				
				simplex.wreta(r,s, d_);
			}
			
			if(!infinite){
				simplex.price=-simplex.multiplyVectrices(simplex.subVector(simplex.c, simplex.base), simplex.b_);
			}
			else{
				simplex.price=-Double.POSITIVE_INFINITY;
			}
			
			long endzeit=System.currentTimeMillis();
			
			long dauer=endzeit-startzeit;
			System.out.println("Kosten: "+simplex.price);
			System.out.println("Laufzeit( in ms): "+dauer);
			
			
			//write output
			try{
				FileWriter writer= new FileWriter(output, false);
				String opt_value=Double.toString(simplex.price)+"\n";
				writer.write(opt_value);
				writer.close();
				simplex.conv.write(args[1], simplex.b_, simplex.base);
			}
			catch (IOException e) {
				e.printStackTrace();
			}
			
		}catch(IllegalArgumentException e) {System.out.println(e.getMessage());}
		
	}
}